package com.ljy.my_study.leetcode.电话号码的字母组合;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lijunying
 * @date 2020/8/7 10:50
 */
public class TestMain {

//    给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
//
//    给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
//
//     九宫格
//
//    示例:
//
//    输入："23"
//    输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
//    说明:
//    尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

    public static void main(String[] args) {
        System.out.println(new TestMain().letterCombinations("23"));
    }

    public List<String> letterCombinations(String digits) {
        if(digits==null||"".equals(digits)){
            return new ArrayList<>();
        }
        int[][] indexArr=new int[10][2];
        int start=0;
        int end=3;
        for(int i=2;i<10;i++){
            int len=3;
            if(i==7||i==9){
                len=4;
            }
            if(i==2){
                indexArr[i]=new int[]{start,end};
            }else{
                indexArr[i]=new int[]{end,end+len};
            }
            start=indexArr[i][0];
            end=indexArr[i][1];
        }
        List<String> list=new ArrayList<>();
        dfs(new StringBuilder(),list,digits,0,indexArr);
        return list;
    }

    private void dfs(StringBuilder sb,List<String> list, String digits,int index,int[][] indexArr){
        if(digits.length()==index){
            list.add(sb.toString());
            return;
        }
        int[] arr=indexArr[digits.charAt(index)-'0'];
        for(int i=arr[0];i<arr[1];i++){
            StringBuilder newSb=new StringBuilder(sb);
            newSb.append((char)('a'+i));
            dfs(newSb,list,digits,index+1,indexArr);
        }
    }
}
